public class SearchMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        int len1 = matrix.length, len2 = matrix[0].length;
        for (int i = 0; i < len1; i++) {
            if (target <= matrix[i][len2-1]) {
                if (target == matrix[i][len2-1]) return true;
                int left = 0, right = len2 - 1;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (matrix[i][mid] < target) left = mid + 1;
                    else {
                        right = mid;
                    }
                }
                return matrix[i][left] == target;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        SearchMatrix searchMatrix = new SearchMatrix();
        int[][] matrix = {{1,4,7,11,15}, {2,5,8,12,19}, {3,6,9,16,22}, {10,13,14,15,24}};
        System.out.println(searchMatrix.searchMatrix(matrix, 5));
    }
}
